package com.zhugang.week04;

/**
 * @program algorithms
 * @description: multiply
 * @author: chanzhugang
 * @create: 2022/06/24 16:24
 */
public class Multiply2 {

    /**
     * 递归乘法
     *
     * @param A
     * @param B
     * @return
     */
    public int multiply(int A, int B) {
        int n = Math.min(A, B);
        int k = Math.max(A, B);
        if (n == 1) {
            return k;
        }
        // n个k相加 = （n/2个k相加）+（n/2个k相加）+ 0（或k）
        int halfVal = multiply(n / 2, k);
        if (n % 2 == 1) {
            return halfVal + halfVal + k;
        } else {
            return halfVal + halfVal;
        }
    }
}